#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.

"""

"""

class NumberCombine:
    def __init__(self, target_num):
        self.num = target_num
        self.memory = {}            # dp的记忆体, 空间换时间, 递归中已经计算过的子问题做记录

        self.hit_memory_cnt = 0

    def partion_cnt(self):
        return self.partion_cnt_rec_from_max(self.num, self.num)

    def partion_cnt_rec_from_max(self, num, max_begin):
        # 考虑对分割进行排序的情况, 按照首位最大值的情况递归处理(与最小值首位情况同构, 顺序相反)
        # 返回值: 对num进行分割, 分割值中最小的数从max_begin开始的计数
        key = (num, max_begin)

        if num == 1:
            return 1

        if num == 0:
            return 1

        cnt = self.memory.get(key)
        if cnt is not None:
            self.hit_memory_cnt += 1
            return cnt

        cnt = 0
        # for new_max_begin in range(1, max_begin+1):
        for new_max_begin in range(max_begin, 0, -1):
            remain = num - new_max_begin
            if remain < new_max_begin:
                cnt += self.partion_cnt_rec_from_max(remain, remain)
                # print("call max", remain, " ", remain)
            else:
                # print("call trival", remain, " ", new_max_begin)
                cnt += self.partion_cnt_rec_from_max(remain, new_max_begin)

        self.memory[key] = cnt
        return cnt


def test():
    # from wiki: https://en.wikipedia.org/wiki/Partition_(number_theory)
    ans_lst = [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604]

    for num, cnt in enumerate(ans_lst):
        # print(num, cnt)
        n = NumberCombine(num)
        assert n.partion_cnt() == cnt

    # 总共5个人在餐馆, 一张桌子最多坐3个人(可以坐(1,2,3)个人), 问几种分割法
    n = NumberCombine(5)
    print( n.partion_cnt_rec_from_max(5, 3) )

    n = NumberCombine(50)
    assert n.partion_cnt() == 204226

    n = NumberCombine(120)
    assert n.partion_cnt() == 1844349560

    n = NumberCombine(130)
    # print( n.partion_cnt() )
    assert n.partion_cnt() == 5371315400

def main():
    print("start main")
    test()


if __name__ == "__main__":
    main()
